class Solution
{
public:
    class Wrong
    {
        // 这个做法不对，价值和最大不一定开销最大，还要考虑根节点大小
        long long maxOutput(int n, vector<vector<int>> &edges, vector<int> &price)
        {
            unordered_map<int, vector<int>> adjTable;
            for (auto &edge : edges)
            {
                adjTable[edge[0]].push_back(edge[1]);
                adjTable[edge[1]].push_back(edge[0]);
            }

            int maxStart = 0;
            long long maxPrice1 = 0;
            unordered_set<int> visited1;
            visited1.insert(0);
            dfs(0, adjTable, visited1, price, price[0], maxPrice1, maxStart);

            int maxEnd = 0;
            long long maxPrice2 = 0;
            unordered_set<int> visited2;
            visited2.insert(maxStart);
            dfs(maxStart, adjTable, visited2, price, price[maxStart], maxPrice2, maxEnd);

            return maxPrice2 - min(price[maxStart], price[maxEnd]);
        }

        void dfs(int node, unordered_map<int, vector<int>> &adjTable, unordered_set<int> &visited, vector<int> &price, long long curPrice, long long &maxPrice, int &maxPriceReachNode)
        {
            if (curPrice >= maxPrice)
            {
                maxPrice = curPrice;
                maxPriceReachNode = node;
            }
            for (int adjNode : adjTable[node])
            {
                if (!visited.count(adjNode))
                {
                    visited.insert(adjNode);
                    dfs(adjNode, adjTable, visited, price, curPrice + price[adjNode], maxPrice, maxPriceReachNode);
                }
            }
        }
    };
};